package com.litchishell.easy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author LitchiShell
 * @description: 题目21：合并两个有序链表
 * @create 2022-08-20
 */
public class Solution006 {

    // 常规解法
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode();
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        List<Integer> list = new ArrayList<>();
        saveValue(list, list1);
        saveValue(list, list2);
        Collections.sort(list);
        Collections.reverse(list);
        Stack<Integer> stack = new Stack<>();
        for (Integer integer : list) {
            stack.push(integer);
        }
        createValue(stack, result);
        return result;
    }

    public static void saveValue(List<Integer> list, ListNode list1) {
        if (list1 != null) {
            list.add(list1.val);
            saveValue(list, list1.next);
        }
    }

    public static void createValue(Stack<Integer> stack, ListNode list1) {
        if (!stack.isEmpty()) {
            list1.val = stack.pop();
            list1.next = stack.isEmpty() ? null : new ListNode();
            createValue(stack, list1.next);
        }
    }

    // 官方解法
    public ListNode mergeTwoListsCopy(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoListsCopy(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoListsCopy(l1, l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(5, null);
        ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
        ListNode listNode = mergeTwoLists(list1, list2);
        System.out.println(1);
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
